#include "DoubleLinkList.h"
#include <iostream>
DoubleLinkList::DoubleLinkList():head(new Node),size(0)
{
    head->data = 0;
    head->next = head->prev = nullptr;
    head = m_tail;
}

DoubleLinkList::~DoubleLinkList()
{
    while(head != nullptr)
    {
        Node*nextNode = head->next;
        delete head;
        head = nextNode;
    }
}

void DoubleLinkList::InsertTail(ElementType element)
{
   Node *newNode = CreateNode(element);
   Node *end = GetEnd();
   end->next = newNode;
   newNode->prev = end;
   size++;
}

void DoubleLinkList::InsertHead(ElementType element)
{
    Node *newNode = CreateNode(element);

    newNode->next = head->next;
    newNode->prev = head;
    if(size > 0)
        head->next->prev = newNode;
    head->next = newNode = newNode;
    size++;
}

void DoubleLinkList::InsertByIndex(int index, ElementType element)
{   
     if(index < 0 || index > size)
    {
        printf("插入的的位置非法:%d len : %d\n",index,size);
        return;
    }
    Node* travelPoint = head;
    Node *newNode = CreateNode(element);
    if(index == size)
    {   
        travelPoint = m_tail;
        newNode->next = nullptr;
        newNode->prev = travelPoint;
        travelPoint->next = newNode;
        m_tail = newNode;
        size++;
    }
    else
    {
        for(int i = 0;i < index;i++) //因为有头节点的存在所以取i < index
        {
            travelPoint = travelPoint->next;
        }
            newNode->next = travelPoint->next;
            newNode->prev = travelPoint;
            travelPoint->next->prev = newNode;
            travelPoint->next = newNode;
            size++;
    }
}

void DoubleLinkList::RemoveByIndex(int index)
{   
    if(index < 0 || index >= size)
    {
        printf("删除的位置非法:%d len : %d\n",index,size);
        return;
    }
    Node* travelPoint = head;
    for(int i = 0; i < index;i++)
    {
        travelPoint = travelPoint->next;
    }

    Node*freeNode = travelPoint->next;
    if(index == 0)
    {   
        head->next = freeNode->next;
        freeNode->next->prev = nullptr;
        delete freeNode;
        size--;
    }
    else if(index == size-1)
    {
        travelPoint->next = nullptr;
        delete freeNode;
        size--;
    }
    else
    {
        travelPoint->next = freeNode->next;
        freeNode->next->prev = travelPoint;
        delete freeNode;
        size--;
    }
}

void DoubleLinkList::RemoveByElement(ElementType element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == element)
        {   
            if(travelPoint->next->prev == nullptr)
            {
                Node*freeNode = travelPoint->next;
                travelPoint->next = freeNode->next;
                freeNode->next->prev = nullptr;
                delete freeNode;
                size--;
            }
            else if(travelPoint->next->next == nullptr)
            {
                travelPoint->next = nullptr;
                size--;
            }
            else
            {
                Node*freeNode = travelPoint->next;
                travelPoint->next = freeNode->next;
                freeNode->next->prev = travelPoint;
                delete freeNode;
                size--;
            }
        }
        else
            travelPoint = travelPoint->next;
    }
}

void DoubleLinkList::UpdateByIndex(int index, ElementType newValue)
{
    Node *travelPoint = head;
    for(int i = 0;i <= index;i++)
        travelPoint = travelPoint->next;
    travelPoint->data = newValue;
}

void DoubleLinkList::UpdateByElement(ElementType oldValue, ElementType newValue)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == oldValue)
            travelPoint->next->data = newValue;
        travelPoint = travelPoint->next;   
    }
}

ElementType &DoubleLinkList::operator[](int index)
{
    Node *travelPoint = head;
    for(int i = 0;i <= index;i++)
    travelPoint = travelPoint->next;
    return travelPoint->data;
}

void DoubleLinkList::BubbleSort()
{
    for(int i = 0;i < size-1;i++)
    {   
        Node * travelPoint = head;//每次扫描链表回到起始点
        for(int j = 0;j < size-i-1;j++)
        {   
            if(travelPoint->next->prev == nullptr&&travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *P = travelPoint->next;
                Node *N = P->next;
                P->next = N->next;
                N->next->prev = P;
                N->prev = nullptr;
                P->prev = N;
                travelPoint->next = N;
            }
            if(travelPoint->next->next->next == nullptr&&travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *P = travelPoint->next;
                Node *N = P->next;
                P->next = nullptr;
                N->next = P;
                N->prev = travelPoint;
                P->prev = N;
                travelPoint->next = N;
            }
            if(travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *P = travelPoint->next;
                Node *N = P->next;
                P->next = N->next; 
                N->next->prev = P;
                N->next = P;
                N->prev = travelPoint;
                P->prev = N;
                travelPoint->next = N;
            }
            travelPoint = travelPoint->next;
        }
    }
}

void DoubleLinkList::FastSort()
{
    FastSort(head->next,nullptr); 
}

DoubleLinkList DoubleLinkList::Merge(const DoubleLinkList &l)
{   
    DoubleLinkList result;

    Node *p1 = this->head->next;
    Node *p2 = l.head->next;
    while(p1 !=nullptr && p2 !=nullptr)
    {
        if(p1->data < p2->data)
        {
            result.InsertTail(p1->data);
            p1 = p1->next;
        }
        else
        {
            result.InsertTail(p2->data);
            p2 = p2->next;
        }
        
    }
        while(p1)
        {
            result.InsertTail(p1->data);
            p1 = p1->next;
        }

        while(p2)
        {
            result.InsertTail(p2->data);
            p2 = p2->next;
        }

        return result;
}

int DoubleLinkList::BinarySearch(ElementType element)
{   
    FastSort();

    int left = 0;
    int right = size-1;
    Node*current = head;
    int index = -1;
    while(current != nullptr)
    {
        int middle = (left + right) / 2;
         // 在链表中移动到中间位置
        if (index < middle){
            current = current->next;
            index = index + 1;
        }
        else if (index > middle)
            {current = current->prev;
            index = index - 1;}
          // 当前节点是中间节点
        else
        {
            if (current->data == element)
                return index;
            else if (current->data < element)
                left = middle + 1;
            else
                right = middle - 1;
        }
        // 更新索引
        
    }
    return -1;
}

void DoubleLinkList::show()
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        std::cout<<travelPoint->next->data<<" ";
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
}

void DoubleLinkList::ReserveShow()
{
    Node *end = GetEnd();
    while(end != head)
    {
        std::cout<<end->data<<" ";
        end = end->prev;
    }
     std::cout<<std::endl;
}

void DoubleLinkList::Reserve()
{   
    Node * travelPoint = head->next;
    Node* end = GetEnd();
    std::swap(travelPoint->prev,travelPoint->next);
    travelPoint->next = nullptr;
    while (travelPoint->prev != nullptr) 
    {
        travelPoint = travelPoint->prev;
        std::swap(travelPoint->prev,travelPoint->next);   
    }
    end->prev = head;
    head->next = end;
}

void DoubleLinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

DoubleLinkList::Node *DoubleLinkList::GetEnd()
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
        travelPoint = travelPoint->next;
    return travelPoint;
}

DoubleLinkList:: Node *DoubleLinkList::CreateNode(ElementType element)
{
    Node *newNode = new Node;
    newNode->data = element;
    newNode->next = newNode->prev = nullptr;
    return newNode;
}

void DoubleLinkList::FastSort(Node *start, Node *end)
{
    if(start == end)
        return;

    Node* temp = start; //基准值
    Node* p1 = start; //left
    Node* p2 = p1->next; //right

    while(p2 != end)
    {   
        //比基准值小
        if(p2->data < temp->data)
        {
            p1 = p1->next;
            std::swap(p1->data,p2->data);
        }
        p2 = p2->next;
    }
    std::swap(p1->data,temp->data); //将基准值和p1的值互换

    FastSort(start,p1);
    FastSort(p1->next,end);
}

DoubleLinkList::Node *DoubleLinkList::Reserve2(Node *node)
{   
    if(node->next == nullptr)
    {
        return node;
    }
    else
    {
        Node* newHeader = Reserve2(node->next);
        node->next->next = node;
        node->next = nullptr;
        return newHeader;
    }
}

int DoubleLinkList:: getSize()
 {
    return size;
 }
